package bishi.qianxin;

import java.util.HashSet;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/08/07 15:33
 */
public class two {
    public static void main(String[] args) {
        System.out.println(getMaximumResource(new int[][]{{1, 0, 7}, {2, 0, 6}, {3, 4, 5}, {0, 3, 0}, {9, 0, 20}}));
    }

    static int[][] fx = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    public static int getMaximumResource(int[][] grid) {
        // write code here
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;
        int max = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, grid[i][j]);
                set.add(i * 100000 + j);
                for (int[] dis : fx) {
                    int x = dis[0] + j;
                    int y = dis[1] + i;
                    if (x < 0 || x >= col) continue;
                    if (y < 0 || y >= row) continue;
                    if (grid[y][x]==0) continue;
                    max = Math.max(max, dfs(grid, y, x, grid[i][j] + grid[y][x], set));
                }
                set.remove(i * 100000 + j);
            }
        }
        return max;
    }

    public static int dfs(int[][] grid, int i, int j, int now, HashSet<Integer> set) {
        set.add(i * 100000 + j);
        int max = now;
        for (int[] dis : fx) {
            int x = dis[0] + j;
            int y = dis[1] + i;
            if (x < 0 || x >= grid[0].length) continue;
            if (y < 0 || y >= grid.length) continue;
            if (set.contains(y * 100000 + x)) continue;
            if (grid[y][x]==0) continue;
            max = Math.max(dfs(grid, y, x, now + grid[y][x], set), max);
        }
        set.remove(i * 100000 + j);
        return max;
    }
}
